#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <mpi.h>


/* Struct para uma palavra do arquivo */
typedef struct 
{
	char *palavra;
}str;


/* Armazena em uma tabela as strings do arquivo de acordo com seu tamanho */
typedef struct 
{
	int tamanho;				/* Quantidade de elementos para um determinado tamanho */
	str *vetor;			/* Vetor de strings */
}string_table;

/* Gera um caracter aleatório (a~z) */
int rand_char()
{
	return 97 + (rand()%26);
}

/* Retorna verdadeiro caso seja uma letra minúscula ou maiúscula */
int isCaracter(char c)
{
	if((c >= 65 && c <= 90) || (c >= 97 && c <= 122))
		return 1;
	else 
		return 0;
}


void main(int argc, char *argv[])
{
	FILE *pFile;
	char c;
	char string[60];
	char string_final[60];
	int offset = 0;
	int i=0,j=0;
	int id;
	int p;
	int count, count_words=0;
	int cnt[12];
	int disp[12];
	char ch[4];
	int aux;
	int count_words2 = 0;
	int aux2 = 1;
	int timer;
	MPI_Status status;

	struct timeval start, end; 			/* Variáveis para guardar o tempo atual */

    gettimeofday(&start, NULL); 		/* Pega o tempo antes da execução do algoritmo */
	
	MPI_Init(&argc, &argv);

	MPI_Comm_rank(MPI_COMM_WORLD, &id);	/* Armazena o id do processo */
	MPI_Comm_size(MPI_COMM_WORLD, &p);	/* Armazena a quantidade de nós */

	srand(time(NULL)+id);				/* Gera uma semente para para a geração de número aleatórios */

	/* Aloca a tabela de strings onde será feito o pré-processamento do arquivo */

	string_table *table;

	str *table_realloc;

	table = (string_table *) calloc(50, sizeof(string_table));

	/* Abre uma stream para o arquivo */

	pFile = fopen("palavras.txt", "r");

	if(id == 0)
	{
		printf("Realizando pre-processamento...\n");
	}
	

	/* Pré-Processamento do Arquivo: 														*/
	/* Armazena as palavras do arquivo em uma tabela de acordo com seu tamanho 				*/
	/* Caso a palavra tenha tamanho 2, será armazenada em um vetor na posĩcao 2 da tabela 	*/
	/* E assim para todos os tamanhos 														*/
	do
	{
		c = getc(pFile);

		/* Verifica se é uma letra */
		if(isCaracter(c))
		{
			string[offset] = c;

			offset++;
		}
		/* Caso encontre uma vírgula, estamos no separador do arquivo, e devemos armazenar a palavra */
		else if(c == 44)
		{
			string[offset] = '\0';

			table_realloc = (str *) realloc(table[offset].vetor, (++(table[offset].tamanho)) * sizeof(str));

			table[offset].vetor = table_realloc;

			table[offset].vetor[(table[offset].tamanho)-1].palavra = (char *) malloc((offset+1) * sizeof(char));

			strcpy(table[offset].vetor[(table[offset].tamanho)-1].palavra, string);

			offset = 0;

			count_words++;
		}
		/* Caso encontre um caracter que não seja uma letra, pula para o próximo candidato a palavra */
		else
		{
			do
			{
				c = getc(pFile);

			}while (c != 44 && c != EOF);

			offset = 0;

			count_words++;
		}
		
	}while(c != EOF);
	

	/* Fecha o arquivo */
  	fclose (pFile);

  	if(id == 0)
	{
		printf("Pre-processamento realizado!\n\n");

		printf("Gerando caracteres aleatorios...\n");
	}
  	
  	/* Comunicação entre os nós ao gerar as palavras entre tamanho 1 e 10: */
  	/* Neste loop, a função MPI_Scatterv é utilizada para que um único processo distribua uma quantidade de elementos */
  	/* para todos os outros processos em um comunicador, incluindo ele mesmo.										  */
  	/* Dessa maneira, dividimos a palavra atual entre os 10 nós utilizados, para que cada um fique encarregado de     */
  	/* gerar um caracter aleatório. 																				  */
  	/* Ao encontrar o caracter certo, utilizamos a função MPI_Gatherv, para que todos os processos juntem em um único */
  	/* processo o resultado final.																					  */

  	/* Palavras de tamanho entre 1 e 10: 													*/
  	/* Apenas quando palavras de tamanho 10 são analisadas todos os 10 nós geram caracteres */
  	/* Quando por exemplo, geramos palavras de tamanho 4, 6 nós não serão utilizados		*/
  	for(j=1;j<=p;j++)
  	{
		if(id >= j)
			count = 0;
		else
			count = 1;

		/* Preenchimento dos vetores utilizados nas funções MPI_Scatterv e MPI_Gatherv */
		for(i=0;i<p;i++)
		{
			if(i >= j)
			{
				cnt[i] = 0;
				disp[i] = 0;
			}
			else
			{
				cnt[i] = 1;
				disp[i] = i;			
			}
		}
		
		/* Percorre todos as palavras da tabela de acordo com o tamanho */
		for(i=0;i<table[j].tamanho;i++)
		{
			MPI_Barrier(MPI_COMM_WORLD);

			/* Distribui entre os processos um ou nenhum caracter de cada palavra, dependendo do tamanho da palavra e do id do processo */
			MPI_Scatterv(table[j].vetor[i].palavra, cnt, disp, MPI_CHAR, ch, count, MPI_CHAR, 0, MPI_COMM_WORLD);

			/* Geração de uma ou nenhuma letra aleatória dependendo do id do processo e do tamanho da palavra */
			if(id < j)
			{
				do
				{
					c = rand_char();
					
				}while((ch[0] != c) && ((ch[0])+32 != c));
			}

			/* Barreira que espera todos os nós gerarem o caracter correto */
			MPI_Barrier(MPI_COMM_WORLD);

			/* Reune, no processo de id = 0, os caracteres gerados aleatoriamente na variável 'string_final' */
			MPI_Gatherv(ch, count, MPI_CHAR, string_final, cnt, disp, MPI_CHAR, 0, MPI_COMM_WORLD);


			/* No nó mestre está armazenado a palavra final gerada aleatoriamente */
			/* O tempo de execução é mostrado durante a execução do código */
			if(id == 0)
			{
				string_final[j] = '\0';

				/* Retirar como comentário a linha de baixo caso queira conferir a string final */

				//printf("Palavra Final:%s\n", string_final);

				count_words2++;		/* Incrementa o número de palavras encontradas */

				/* Imprime o tempo de 1 em 1 porcento dos resultados */
				if(count_words2 > (aux2*(count_words/100)))
				{
					gettimeofday(&end, NULL); 					/* Pega o tempo depois da execução do algoritmo */

				    timer = end.tv_sec - start.tv_sec; 			/* Timer será diferença dada em segundos dos tempos */

					printf("\n\nPorcentagem de palavras encontradas: %d    Tempo: %d seg", (aux2), timer);

					aux2++;
				}
			}
		}
	}

	/*================================================================================*/
	
	/* Palavras de tamanho entre 10 e 20: 											 */
  	/* Todos os 10 nós geram caracteres aleatórios 									 */
  	/* Quando por exemplo, geramos palavras de tamanho 11, o primeiro nó irá gerar 2 */
  	/* caracteres enquanto os outros 9 irão gerar 1 caracter.						 */
	for(j=1;j<=p;j++)
	{
		if(id < j)
			count = 2;
		else
			count = 1;

		/* Preenchimento dos vetores utilizados nas funções MPI_Scatterv e MPI_Gatherv */
		for(i=0;i<p;i++)
		{
			if(i < j)
			{
				cnt[i] = 2;
				disp[i] = i*2;

				aux = 0;
			}
			else
			{
				cnt[i] = 1;
				disp[i] = (j*2)+aux;	

				aux++;		
			}
		}
		
		/* Percorre todos as palavras da tabela de acordo com o tamanho */
		for(i=0;i<table[10+j].tamanho;i++)
		{
			MPI_Barrier(MPI_COMM_WORLD);

			/* Distribui entre os processos um ou nenhum caracter de cada palavra, dependendo do tamanho da palavra e do id do processo */
			MPI_Scatterv(table[10+j].vetor[i].palavra, cnt, disp, MPI_CHAR, ch, count, MPI_CHAR, 0, MPI_COMM_WORLD);


			/* Gera duas letras aleatórias dependendo do id do processo e do tamanho da palavra */
			if(id < j)
			{
				do
				{
					c = rand_char();
					
				}while((ch[0] != c) && ((ch[0])+32 != c));

				do
				{
					c = rand_char();
					
				}while((ch[1] != c) && ((ch[1])+32 != c));
			}
			/* Gera uma letra dependendo do id do processo e do tamanho da palavra */
			else
			{
				do
				{
					c = rand_char();
					
				}while((ch[0] != c) && ((ch[0])+32 != c));

			}
			
			/* Barreira que espera todos os nós gerarem o caracter correto */
			MPI_Barrier(MPI_COMM_WORLD);

			/* Reune, no processo de id = 0, os caracteres gerados aleatoriamente na variável 'string_final' */
			MPI_Gatherv(ch, count, MPI_CHAR, string_final, cnt, disp, MPI_CHAR, 0, MPI_COMM_WORLD);


			/* No nó mestre está armazenado a palavra final gerada aleatoriamente */
			/* O tempo de execução é mostrado durante a execução do código */
			if(id == 0)
			{
				string_final[10+j+1] = '\0';

				/* Retirar como comentário a linha de baixo caso queira conferir a string final */

				//printf("Palavra Final:%s\n", string_final);

				count_words2++;		/* Incrementa o número de palavras encontradas */

				if(count_words2 > (aux2*(count_words/100)))
				{
					gettimeofday(&end, NULL); /* Pega o tempo depois da execução do algoritmo */

				    timer = end.tv_sec - start.tv_sec; /* time será diferença dada em segundos dos tempos */

					printf("\n\nPorcentagem de palavras encontradas: %d    Tempo: %d seg", (aux2), timer);

					aux2++;
				}
			}
		}
	}

	/*================================================================================*/
	
	/* Palavras de tamanho entre 20 e 30: 											 */
  	/* Todos os 10 nós geram caracteres aleatórios 									 */
  	/* Quando por exemplo, geramos palavras de tamanho 21, o primeiro nó irá gerar 3 */
  	/* caracteres enquanto os outros 9 irão gerar 2 caracter.						 */
	for(j=1;j<=p;j++)
	{
		if(id < j)
			count = 3;
		else
			count = 2;

		/* Preenchimento dos vetores utilizados nas funções MPI_Scatterv e MPI_Gatherv */
		for(i=0;i<p;i++)
		{
			if(i < j)
			{
				cnt[i] = 3;
				disp[i] = i*3;

				aux = 0;
			}
			else
			{
				cnt[i] = 2;
				disp[i] = (j*3)+aux;	

				aux++;		
			}
		}
		
		/* Percorre todos as palavras da tabela de acordo com o tamanho */
		for(i=0;i<table[20+j].tamanho;i++)
		{
			MPI_Barrier(MPI_COMM_WORLD);

			/* Distribui entre os processos um ou nenhum caracter de cada palavra, dependendo do tamanho da palavra e do id do processo */
			MPI_Scatterv(table[20+j].vetor[i].palavra, cnt, disp, MPI_CHAR, ch, count, MPI_CHAR, 0, MPI_COMM_WORLD);

			/* Gera 3 letras aleatórias dependendo do id do processo e do tamanho da palavra */
			if(id < j)
			{
				do
				{
					c = rand_char();
					
				}while((ch[0] != c) && ((ch[0])+32 != c));

				do
				{
					c = rand_char();
					
				}while((ch[1] != c) && ((ch[1])+32 != c));

				do
				{
					c = rand_char();
					
				}while((ch[2] != c) && ((ch[2])+32 != c));
			}
			/* Gera 2 letras aleatórias dependendo do id do processo e do tamanho da palavra */
			else
			{
				do
				{
					c = rand_char();
					
				}while((ch[0] != c) && ((ch[0])+32 != c));

				do
				{
					c = rand_char();
					
				}while((ch[1] != c) && ((ch[1])+32 != c));

			}
			
			/* Barreira que espera todos os nós gerarem o caracter correto */
			MPI_Barrier(MPI_COMM_WORLD);

			/* Reune, no processo de id = 0, os caracteres gerados aleatoriamente na variável 'string_final' */
			MPI_Gatherv(ch, count, MPI_CHAR, string_final, cnt, disp, MPI_CHAR, 0, MPI_COMM_WORLD);


			/* No nó mestre está armazenado a palavra final gerada aleatoriamente */
			/* O tempo de execução é mostrado durante a execução do código */
			if(id == 0)
			{
				string_final[20+j+1] = '\0';

				/* Retirar como comentário a linha de baixo caso queira conferir a string final */

				//printf("Palavra Final:%s\n", string_final);

				count_words2++;		/* Incrementa o número de palavras encontradas */

				if(count_words2 > (aux2*(count_words/100)))
				{
					gettimeofday(&end, NULL); /* Pega o tempo depois da execução do algoritmo */

				    timer = end.tv_sec - start.tv_sec; /* time será diferença dada em segundos dos tempos */

					printf("\n\nPorcentagem de palavras encontradas: %d    Tempo: %d seg", (aux2), timer);

					aux2++;
				}
			}
		}
	}

	MPI_Finalize();
}